package com.tgy.tree;

import com.tgy.util.List;
import com.tgy.util.printer.BinaryTreeInfo;

import java.util.*;

/**
 * @Author: tgy
 * @Date: 2020-09-23 16:52
 */



public class BinaryTree<E> implements BinaryTreeInfo {

    protected int size;
    protected Node<E> root;

    public interface ElementOperation<E>{

        E add(E e1,E e2);

        E zero();
    }

    private ElementOperation<E> operation;

    private static enum TraversalTypeEnum{

       /**
        * 前序非递归
        */
       PREORDER,
       /**
        * 前序递归
        */
       PREORDERRECURISION,
       /**
        * 中序非递归遍历
        */
       INORDER,
       /**
        * 中序递归遍历
        */
       INORDERRECURISION,
       /**
        * 后续非递归
        */
       POSTORDER,
       /**
        * 后序递归
        */
       POSTORDERRECURISION,
       /**
        * 层序遍历
        */
       LEVEL
   }

   public static abstract  class  Visitor<E>{

       /**
        * 在递归的时候判断是否退出循环
        */
        public boolean flag;

       /**
        *
        * @return 在非递归的情况下判断是否退出循环
        */
        public abstract boolean stop(E element);
    }


    protected static class Node<E> {

        E element;

        Node<E> left;

        Node<E> right;

        Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        @Override
        public String toString() {

            return element.toString();
        }

        public boolean isLeaf() {

            return Objects.isNull(left) && Objects.isNull(right);
        }

        public int degreed() {

          if (Objects.nonNull(left) && Objects.nonNull(right)) {

            return 2;
          }

          if (Objects.isNull(left) && Objects.isNull(right)) {

            return 0;
          }
           return 1;
        }

      /**
       * 是否是左子树
       * @return
       */
      public boolean isLeft() {

          if (Objects.isNull(parent)) {
            return false;
          }
          return Objects.equals(parent.left,this);
      }

      public boolean isRight() {

        if (Objects.isNull(parent)) {
          return false;
        }
        return Objects.equals(parent.right,this);
      }

    }

    public BinaryTree(ElementOperation<E> operation) {
        this.operation = operation;
    }

    public BinaryTree() {

        this(null);
    }

    public int size() {

        return size;
    }

    public boolean isEmpty(){

        return size != 0;
    }

    public void clear() {

        this.root = null;
        this.size = 0;
    }

    /**
     * 判断二叉树是否包含某个元素,在二叉树中使用中序遍历获取元素
     * @param element 判断的元素
     * @return
     */
    protected boolean contain(E element) {

        if (element == null) {

            return false;
        }

        Node<E> tmpNode = new Node<>(null,null);

        // 查找
        inorderTraversalTree(new Visitor<E>() {
            @Override
            public boolean stop(E element) {

                if (element.equals(element)) {

                    tmpNode.element = element;
                    return true;
                }
                return false;
            }
        });

        return tmpNode.element != null;
    }


    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {

        return ((Node<E>)node).left;
    }

    @Override
    public Object right(Object node) {

        return ((Node<E>)node).right;
    }

    @Override
    public Object string(Object node) {

        return node;
    }

    /**
     * 前序非递归遍历
     * @param visitor
     */
    public void preorderTraversalTree01(Visitor<E> visitor){

        if (Objects.isNull(root)) {

            return;
        }

        Stack<Node<E>> stack = new Stack<>();

        stack.push(root);
        Node<E> node;
        do {
//由于这里要获取栈中的元素，所以root要先进栈
            node = stack.pop();
            if (Objects.nonNull(node.right)) {

                stack.push(node.right);
            }

            if (Objects.nonNull(node.left)) {

                stack.push(node.left);
            }
            if (visitor.stop(node.element)) {
              return;
            }

        }while (!stack.isEmpty());



    }

    /**
     * 前中序递归遍历
     * @param visitor
     */
    public void preorderRecurisionTraversalTree(Visitor<E> visitor) {


    }

    /**
     * 前序非递归遍历,类似层序遍历，容器换成了stack
     * @param visitor
     */
    public void preorderTraversalTree(Visitor<E> visitor){

        if (Objects.isNull(root)) {

            return;
        }


        Stack<Node<E>> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()) {


            Node<E> node = stack.pop();

            if (visitor.stop(node.element)) {

                return;
            }

            if (Objects.nonNull(node.right)) {

                stack.push(node.right);
            }

            if (Objects.nonNull(node.left)) {

                stack.push(node.left);
            }
        }

    }

    /**
     * 前序非递归遍历
     * @param visitor
     */
    public void preorderTraversalTree02(Visitor<E> visitor){


        if (Objects.isNull(root)) {

            return;
        }

        Stack<Node<E>> stack = new Stack<>();

        Node<E> node = root;
        while (true) {


            while (Objects.nonNull(node)) {

                if (visitor.stop(node.element)) {

                    return;
                }

                if (Objects.nonNull(node.right)) {

                    stack.push(node.right);
                }

                node = node.left;
            }

            if (stack.isEmpty()) {

                return;
            }

            node = stack.pop();
        }


    }

    /**
     * 中序非递归遍历
     * @param visitor
     */
    public void inorderTraversalTree(Visitor<E> visitor){

        if (Objects.isNull(root)) {

            return;
        }

        Stack<Node<E>> stack = new Stack<>();

        Node<E> node = root;

        while (true) {

            while (Objects.nonNull(node)) {

                stack.push(node);
                node = node.left;
            }

            if (stack.isEmpty()) {

                return;
            }

            node = stack.pop();

            if (visitor.stop(node.element)) {

                return;
            }

            node = node.right;
        }
    }

    /**
     * 后序非递归遍历
     * @param visitor
     */
    public void postorderTraversalTree(Visitor<E> visitor) {

        if (Objects.isNull(root)) {

            return;
        }

        Stack<Node<E>> stack = new Stack<>();

        stack.push(root);

        Node<E> visitorNode = null;

        while (!stack.isEmpty()) {

            Node<E> node = stack.peek();

            if (node.isLeaf() || (Objects.nonNull(visitorNode) && visitorNode.parent.equals(node))) {

                stack.pop();
                visitorNode = node;
                if (visitor.stop(node.element)) {

                    return;
                }

            }else {

                if (Objects.nonNull(node.right)) {

                    stack.push(node.right);
                }

                if (Objects.nonNull(node.left)) {

                    stack.push(node.left);
                }
            }


        }

    }

    /**
     * 中序非递归遍历
     * @param visitor
     */
    public void inorderTraversalTree02(Visitor<E> visitor){


        if (Objects.isNull(root) || Objects.isNull(visitor)) {

            return;
        }

        Stack<Node<E>> stack = new Stack<>();

        Node<E> node = root;

        for (;;) {

            while (Objects.nonNull(node)) {

                stack.push(node);
                node = node.left;
            }

            if (stack.isEmpty()) {

                return;
            }

            node = stack.pop();
            if (visitor.stop(node.element)) {

                return;
            }
            node = node.right;
        }


    }
    /**
     * 中序非递归遍历
     * @param visitor
     */
    public void inorderTraversalTree03(Visitor<E> visitor){


        if (Objects.isNull(root)) {

            return;
        }

        Stack<Node<E>> stack = new Stack<>();
        Node<E> node = root;

        do {

            while (Objects.nonNull(node)) {

                stack.push(node);
                node = node.left;
            }

            node = stack.pop();

            if (visitor.stop(node.element)) {
                return;
            }

            if (Objects.nonNull(node.right)) {

                node = node.right;
            }else {
                node = null;
            }

        }while (node != null || !stack.isEmpty());

    }

    /**
     * 中序递归遍历
     * @param visitor
     */
    public void inorderRecurisionTraversalTree(Visitor<E> visitor) {


    }


    /**
     * 后序非递归遍历
     * @param visitor
     */
    public void postorderTraversalTree01(Visitor<E> visitor){


        if (Objects.isNull(root)) {

            return;
        }

        Stack<Node<E>> stack = new Stack<>();

        Node<E> node = root;
        Node<E> beforeVisitorNode = null;
        do {

            while (Objects.nonNull(node)) {

                stack.push(node);
                node = node.left;
            }

            node = stack.peek();

            /**
             * 如果是叶子节点，或者 当前节点是父节点的右子树
             */
            if (node.isLeaf() || Objects.equals(node.right,beforeVisitorNode) ||
              (Objects.equals(node.left,beforeVisitorNode) && Objects.isNull(node.right))) {

                stack.pop();
                beforeVisitorNode = node;
                if (visitor.stop(node.element)) {
                    return;
                }
                node = null;
            }else {

                node = node.right;
            }

        }while (node != null || !stack.isEmpty());

    }

    /**
     * 后序递归遍历
     * @param visitor
     */
    public void postorderRecurisionTraversalTree(Visitor<E> visitor) {


    }

  /**
   * 层序遍历
   * @param visitor
   */
  public void levelTraversalTree(Visitor<E> visitor) {

    if (Objects.isNull(root)) {
      return;
    }

    LinkedList<Node<E>> queue = new LinkedList<>();

    queue.offer(root);
    Node<E> node;
    do {

       node = queue.poll();
       if (visitor.stop(node.element)) {

         return;
       }

       if (Objects.nonNull(node.left)) {

         queue.offer(node.left);
       }

       if (Objects.nonNull(node.right)) {

         queue.offer(node.right);
       }

    }while (!queue.isEmpty());

  }

  public Node<E> successorNode(Node<E> node) {

    if (Objects.isNull(node)) {
      return null;
    }

    if (Objects.nonNull(node.right)) {

      node = node.right;
      while (Objects.nonNull(node.left)) {

        node = node.left;
      }

      return node;

    }else {

      while (Objects.nonNull(node.parent)) {

        if (Objects.equals(node.parent.left,node)) {
          return node.parent;
        }
        node = node.parent;
      }
    }

    return null;
  }

  public ArrayList<ArrayList<E>> pathEqualValue(E value) {

        if (Objects.isNull(root)) {
            return null;
        }

        ArrayList<ArrayList<E>> paths = new ArrayList<>();
        Stack<Node<E>> stack = new Stack<>();

//        stack.push(root);
        Node<E> node = root,preNode = null;

        while (true) {

            while (Objects.nonNull(node)) {

                stack.push(node);
                node = node.left;
            }

            if (stack.isEmpty()) {

                break;
            }

            node = stack.peek();
            if (node.isLeaf()) {

                addPath(paths, new ArrayList<>(stack.subList(0, stack.size())),value);
            }

            if (node.isLeaf() || (Objects.nonNull(preNode) && (preNode.equals(node.right) || (Objects.isNull(node.right) && preNode.equals(node.left))))) {

                stack.pop();
                preNode = node;
                node = null;
            }else {

                node = node.right;
            }
        }

      return paths;
  }

  private void addPath(ArrayList<ArrayList<E>> paths,ArrayList<Node<E>> path, E value) {

      E tmp = operation.zero();

      ArrayList<E> list = new ArrayList<>();

      for (Node<E> eNode : path) {

          tmp = operation.add(tmp,eNode.element);
          list.add(eNode.element);
      }
//
      if (tmp.equals(value)) {
          paths.add(list);
      }
  }

  /**
   * 通过 元素找到元素对应的node
   * @param element
   * @return
   */
  protected Node<E> elementOfNode(E element) {

      if (Objects.isNull(root)) {
        return null;
      }

      Stack<Node<E>> stack = new Stack<>();

      Node<E> node = root, beforeNode = null;
      do {
        while (Objects.nonNull(node)) {

          stack.push(node);
          node = node.left;
        }

        node = stack.peek();

        if (node.isLeaf() || Objects.equals(node.right,beforeNode) ||
          (Objects.isNull(node.right) && Objects.equals(node.left,beforeNode))) {

          stack.pop();
          beforeNode = node;
          if (Objects.equals(node.element,element)) {

            return node;
          }
          node = null;
        }else {

          node = node.right;
        }

      }while (!stack.isEmpty());

      return null;
  }

//    protected Node<E> nodeOfElement(E element, TraversalTypeEnum traversalTypeEnum) {
//
//        if (traversalTypeEnum == null) {
//
//            traversalTypeEnum = TraversalTypeEnum.INORDER;
//        }
//
//        Node<E> tmpNode = new Node<>(null,null);
//        final TraversalTypeEnum typeEnum  = traversalTypeEnum;
//        new Visitor<E>(){
//
//            @Override
//            public boolean stop(E el) {
//
//                if (element.equals(el)) {
//
//
//                }
//
//                if (typeEnum == TraversalTypeEnum.INORDERRECURISION ||
//                        typeEnum == TraversalTypeEnum.POSTORDERRECURISION ||
//                        typeEnum == TraversalTypeEnum.PREORDERRECURISION) {
//
//                }
//
//                return false;
//            }
//        };
//
//        switch (traversalTypeEnum) {
//
//            case LEVEL:
//                break;
//            case INORDER:
//                break;
//            case PREORDER:
//                break;
//            case POSTORDER:
//                break;
//            case INORDERRECURISION:
//                break;
//            case PREORDERRECURISION:
//                break;
//            case POSTORDERRECURISION:
//                break;
//        }
//
//
//        return null;
//    }
}
